import java.util.ArrayList;
import java.util.Arrays;

/**
 * \* Created with IntelliJ IDEA.
 * \* User: 冯若航
 * \* Date: 2021/5/15
 * \* Time: 21:30
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class 最接近的三数之和 {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        //不能初始化为MAX_VALUE, 因为target为负数的时候，算距离的时候会溢出，比如abs(MAX_VALUE-(-1))
        int res=nums[0]+nums[1]+nums[2];
        for(int i=0;i<nums.length;i++){
            int left=i+1;
            int right= nums.length-1;
            while (left<right){
                // 判断最小值
                int min = nums[i] + nums[left] + nums[left + 1];
                if(target < min){
                    if(Math.abs(res - target) > Math.abs(min - target)){
                        res = min;
                    }
                    break;
                }
                //判断最大值
                int max = nums[i] + nums[right] + nums[right - 1];
                if(target > max){
                    if(Math.abs(res- target) > Math.abs(max - target)){
                        res = max;
                    }
                    break;
                }

                int sum=nums[i]+nums[left]+nums[right];
                if(Math.abs(sum-target)<Math.abs(res-target)){
                    res=sum;
                }
                if(sum<target){
                    left++;
                    //去重
                    while (left<right&&nums[left]==nums[left-1]){
                        left++;
                    }
                }else {
                    right--;
                    //去重
                    while (left<right&&nums[right]==nums[right+1]){
                        right--;
                    }
                }
            }
            // 解决nums[i]重复
            while(i<nums.length-2 && nums[i] == nums[i+1]){
                i++;
            }
        }
        return res;
    }
}